Digital images may be formatted as contone (continuous tone) images having a wide range of tonal values or may be formatted as coarsely quantized images having a limited number of tonal values, such as two levels for a binary image. Digital halftoning is a process of transforming a contone image to a coarsely quantized image. Digital halftoning is an important step in printing or displaying digital images possessing contone color tones because most printing processes are operating in a binary mode. Examples of such marking processes are offset printing presses, xerography, and ink-jet printing. In these processes, for each color separation of an image, a corresponding colorant spot is either printed or not printed at any specified image location, or pixel. Digital halftoning controls the printing of color dots formed by combinations of colorant spots of a colorant set, where the spatial averaging of the printed colorant dots, such as by the human visual system, provides the illusion of the required continuous tones.
Digital images and the resulting prints are formed of one or more colorant separations, also referred to as “color separations.” A monochrome image is formed of one colorant separation, typically black. Process color images are typically constructed of cyan, magenta, yellow, and black separations. Duotone and tritone images are formed of two and three separations, respectively. Spot color images have multiple colorant separations, where at least one colorant is positioned spatially non-overlapping with other colorants. Extended colorant set images typically include the process-color colorant separations plus one or more additional colorant separations such as green, orange, violet, red, blue, white, varnish, light cyan, light magenta, gray, dark yellow, metallics, and so forth. In the present teachings, we will use the terms “color images”, “color dots”, “color spots”, “colorant” and similar language to refer to images and marking systems with any number of colorants. The teachings herein apply particularly to any individual color separation of a digital image and resulting print, where that digital image or print can be composed of one or more separations. With the advent of computers, it is desirable for graphic artists and others to manipulate contone images and print them as halftone images. However, typical computer printers and typesetters are incapable of printing individual halftone dots in an infinite number of sizes. Instead, each halftone dot of a printed picture is in turn comprised of a collection of discrete, smaller “spots” or “pixels”, which are generally the smallest marks a printer or typesetter can make.
A common halftone technique is called screening, which compares the required continuous color tone level of each pixel for each color separation with one or more predetermined threshold levels. The predetermined threshold levels are typically defined for halftone cells that are tiled to fill the plane of an image, thereby forming a halftone screen of threshold values. At a given pixel, if the required color tone level is greater than the halftone threshold level for that pixel, a “1” is generated in the halftone output, so that a colorant spot is printed at that specified pixel in the subsequent printing operation. If the required color tone at a given pixel is less than the halftone threshold level for that pixel, a “0” is generated in the halftone output, so that a colorant spot is not printed at that specified pixel in the subsequent printing operation. The output of the screening process is a binary pattern that controls the printing of multiple small spots or pixels that are printed. The printed spots can be grouped or “clustered” to form print structures that are relatively stable for a given printing process. These clusters are referred to as “clustered-dots” or “dots”, and they are regularly spaced as determined by the size, shape, and tiling of the halftone cell. Conventional periodic halftone screens and halftone screen outputs can be considered as two-dimensional repeated patterns, possessing two fundamental spatial frequencies, which are completely defined by the geometry of the halftone screens.
In this manner, a “digital screen” is created as an array of cells with pixels having threshold values. Each pixel has a set position and a set threshold value within the cell. Likewise, each cell has a set position within the digital screen. To create a halftone image, a contone image is broken down into an array of pixel-sized samples, and the gray level of each contone sample is stored. Next, each contone sample is compared with the halftone threshold value of the corresponding pixel in the halftone screen, and the pixel is darkened in the subsequent print image if the gray level of the contone sample is greater than the threshold value for that pixel. All the pixels of the digital screen are at set positions with respect to one another, such that a contone sample from the “top-left” of the picture would be compared with a pixel at the “top-left” of the digital screen. In other words, each digital screen pixel has a position which corresponds with and is associated with a position on the original contone picture.
Halftoning attempts to render images to printable form while avoiding unwanted visual texture, known as moiré, and tone reproduction irregularities. The two key aspects of halftone screen design are the geometry of periodic dot placement and the shape of the halftone dots. Controlling halftone dot shape has been a lower priority in laser printers because printer pixel resolution, typically measured in rasters per inch referring to the number of smallest printable spots per unit length, has been too low. Consider, for example, the task of controlling dot shape of a 212 cell per inch (cpi) 45° halftone screen used with a printer having a resolution of 600 rasters/inch, where the halftone cell is only two rasters in height. As laser printing resolutions reach 2400 rasters/inch, and greater, controlling halftone dot shape provides a greater impact in improving a printed image.
As pixel resolution has increased with advancements in processor speed, memory capacity, printer and/or display capability, and the like, new options in halftone geometry have arisen. One area of development has been the so-called 2nd generation stochastic screens, where nuclei (seeds) are placed in a stochastic manner using frequency modulation (FM) up to a particular gray level, then grown in size using amplitude modulation (AM) above that level. This approach leads to a limit of the highest allowable seed frequency, which is uniquely determined by the gray level at which the transition from FM to AM occurs. Conventional approaches have attempted to adjust seed frequency according to image busyness to improve detail rendition, but examples produced using such methods show relatively poor quality, as is described in co-pending U.S. patent application Ser. No. 13/108,235, which is hereby incorporated by reference in its entirety herein.
One class of methods of growing these dots operates in the frequency domain. These “green noise”-like methods adjust a frequency spectrum while neglecting fundamental design principles relating to dot shape and touching.
A second class of 2nd generation stochastic screens uses random seeds, then applies a fixed threshold array to control growth around the seeds. While these methods attempt to control growth in the spatial domain, where better control is possible, a fixed threshold array on random seeds tends to produce high graininess and poor touch points.
A third class attempts to use parameters to control the growth within a Voronoi tessellation formalism. These methods seem to be using a sound strategy of defining a spatial tessellation and attempting to control growth and touching between the tiles for the purposes of print-to-print stability and uniformity. But, the growth control seems to be quite suboptimal, offering much less control than is available for growing periodic dots. The lack of control not only affects stability and uniformity, but does not allow dot shaping for aesthetic purposes, such as using rounder dots for faces, squarer sharper dots for graphics, extended highlight dots (avoid touching until into the shadows) and extended shadow dots (which touch early and focus on hole shape), as is described in co-pending U.S. patent application Ser. No. 13/096,429, which is hereby incorporated by reference in its entirety herein.
Watermarking images refers to a set of technologies that embed information into an image. The information may be embedded for a variety of reasons including identifying authorship, creation details, counterfeit prevention, rendering details, and information on content. Most existing watermarking methods apply to contone images and are not robust to the printing process. Halftone-based watermarking allows data embedding in images as part of the printing process. The embedded data can be used for a variety of applications such as ownership protection, authentication, covert communication, and any other usage that can benefit from additional information. Most existing halftone-based watermarking methods are designed for 1st generation stochastic screens (FM) as described in, e.g., U.S. Pat. Nos. 5,790,703 and 5,734,752; periodic clustered-dot screens (AM) as described in U.S. Pat. Nos. 6,252,971 and 7,286,682 as well as in Oztan and Sharma's “Continuous phase modulated halftones and their application to halftone data embedding” (ICASSP 2006); or error diffusion as is described in U.S. Pat. No. 7,660,429. The foregoing references are hereby incorporated by reference in their entireties herein. 2nd generation stochastic halftones (FM to AM) are becoming increasingly popular due to the increased resolution of new printing devices, and they overcome some of the issues associated with periodic screens and 1st generation stochastic halftones. There is a need in the art for systems and methods that facilitate watermarking 2nd generation stochastic halftones.